class Solution {
public:
    vector<string> ret;
    bool is(string ss){
        int sum = 0;
        if(ss.size() > 1 && ss[0] == '0') return false;
        
        for(int i = 0;i < ss.size();i++){
            sum = sum * 10 + (ss[i] - '0');
            if(sum > 255) return false;
        }
        return true;
    }
    void backtrace(string& s,int cur,int sum){
        if(sum == 4){
            if(cur == s.size()){
                ret.push_back(s);
                ret.back().pop_back();
            }
            return;
        }
        if(cur >= s.size() && sum < 4) return;
        for(int i = cur;i < s.size();i++){
            string ss = s.substr(cur,i - cur + 1);
            if(is(ss) == true){
                s.insert(s.begin() + i + 1,'.');
                sum++;
                backtrace(s,i+2,sum);
                sum--;
                s.erase(s.begin() + i + 1);
            }else{
                break;
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        backtrace(s,0,0);
        return ret;
    }
};
